A radar receiver is an electronic device that receives signals in the form of electromagnetic waves in the radio range of approximately 3 kiloHertz (kHz) to 300 gigaHertz (GHz). A sonar receiver is an electronic device that receives signals in the form of acoustic waves. Radio and sonar receivers could be used to locate objects from the echo of signals that are reflected off the objects.
In order to locate objects, both radio and sonar receivers convert respective acquired signals into electrical signals which are then analyzed to extract information carried by the signals. The behavior of signals can be analyzed in the time domain (e.g., how the signal amplitude varies over time) as well as the frequency domain (i.e., the different frequency components that make up the signal), where the Fourier transform mathematically relates these two domains. In addition, a signal can be analyzed as a continuous waveform or, in digital-signal processing (DSP) applications, as a large set of time-domain points. Fast Fourier Transforms (FFTs) refer to algorithms for calculating discrete Fourier transforms (DFTs), as well as their inverses (IDFTs), of signals represented in digital form.
Because of the ubiquitous use of Fourier transforms across signal-processing applications, efforts have been made to improve its execution computationally—hence the many FFT approaches, such as e.g. decimation in time, decimation in frequency, radix-2, radix-4, mixed radix, etc. Still, further improvements in implementing FFTs are desired, in particular in context of radar and sonar applications, and especially those radar and sonar applications that could be implemented at relatively low cost and consume relatively low power.